#include <bits/stdc++.h>
using namespace std;

//1解-->和为0
//求最大连续区间和的起点

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum_gas, sum_cost; sum_cost = sum_gas = 0;
        for(auto& it:gas) sum_gas+=it;
        for(auto& it:cost) sum_cost+=it;
        if(sum_gas < sum_cost) return -1;

        int n=gas.size();
        for(int i=0; i<n; ++i){
            gas[i] -= cost[i];
        }
        int sum = 0;
        int max_sum = 0;
        int start_pos = 0;
        for(int i=n+n-1; i>0; --i){    //2倍长度
            sum+=gas[i%n];
            if(max_sum < sum){
                start_pos = i%n;
                max_sum = sum;
            }
            if(sum<0) sum = 0;
        }
        return start_pos;
    }
};